package com.hackerank.arrays;

/***
 *  Left Rotation   数组左旋
 *  https://www.hackerrank.com/challenges/array-left-rotation/problem
 *  https://www.hackerrank.com/challenges/ctci-array-left-rotation/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays
 *  题目大意：
 *  1、给定一个长度为 N 的数组，向左旋转（左移） M 次 ，输出旋转后的新数组
 *  2、输入 N 和 M
 *  3、输入 N 个数 作为数组元素
 *  4、输出 数组 经过 M 次左旋（移）后的新数组
 *  5、注：最左侧元素左移后到数组的尾部
 *
 *  例：长度为5的数组 [1 2 3 4 5],经过 4次左旋（左移）后为 [5 1 2 3 4]
 *
 *  解题思路：
 *
 *  第一种方法：
 *  1、左移相当于数组起始位置指针右移，可一次性移动，不必按步骤执行
 *  2、假设移动前指针位置定义为 x ，移动 d 之后指针位置y为： y = (x-d+N)%N
 *  3、则在原数组不做调整情况下输出新数组时，原数组的index顺序发生变化，则输出顺序 index = (i+d)%N
 *  4、注：%N操作是为了防止下标越界，实际 INDEXnew = INDEXold - D 故 INDEXold = INDEXnew + d
 *
 *  第二种方法：
 *  1、直接采用链表，header指针一次性向后移动 M 次（注意存在M > N的可能，不过题目中给出 M < N，故不考虑旋转大于一周情况）
 * */
public class LeftRotation {

    public static void main(String[] args) {
        int n = 5;
        int[] a = new int[]{1,2,3,4,5};
        int d = 4;

        for(int i=0;i<a.length;i++){
            System.out.print(a[(i+d)%n] + " ");
        }
    }

    static int[] rotLeft(int[] a, int d) {
        int[] result = new int[a.length];
        for(int i=0;i<a.length;i++){
            result[i] = a[(i+d)%a.length];
        }
        return result;
    }
}
